#include <iostream>
#include <vector>
#include <functional>
using namespace std;

namespace YX
{
    template<typename T,typename Container = vector<T>,class Compare=std::less<T>>
    class priority_queue
    {
        private:
            Container _con;
            Compare _com;
        public:
            
            template<typename InputIterator>
            priority_queue(InputIterator first,InputIterator last)
            {
                while(first!=last)
                {
                    _con.push_back(*first);
                    first++;
                }
                // 建堆---向下建堆
                int i=(_con.size()-1-1)/2;
                while(i>=0)
                {
                    adjust_down(i);
                    i--;
                }
            }

            bool empty()
            {
                return _con.empty();
            }

            size_t size()
            {
                return _con.size();
            }

            const T& top()
            {
                return _con[0];
            }

            // 向上调整算法
            void adjust_up(size_t child)
            {

                size_t parent=(child-1)/2;

                while(child>0)
                {
                    //if(_con[child]>_con[parent])
                    //if(_con[parent]<_con[child])
                    if(_com(_con[parent],_con[child]))
                    {
                        std::swap(_con[child],_con[parent]);
                        child=parent;
                        parent=(child-1)/2;
                    }
                    else 
                    {
                        break;
                    }
                }

            }

            void push(const T& x)
            {
                _con.push_back(x);

                adjust_up(_con.size()-1);

            }

            // 向下调整算法
            void adjust_down(size_t parent)
            {
                size_t child=parent*2+1;

                while(child<_con.size())
                {
                    //if(child+1<_con.size() && _con[child+1]>_con[child])
                    //if(child+1<_con.size() && _con[child]<_con[child+1])
                    if(child+1<_con.size() && _com(_con[child],_con[child+1]))
                    {
                        child++;
                    }

                    //if(_con[child]>_con[parent])
                    //if(_con[parent]<_con[child])
                    if(_com(_con[parent],_con[child]))
                    {
                        std::swap(_con[child],_con[parent]);

                        parent=child;
                        child=parent*2+1;
                    }
                    else 
                    {
                        break;
                    }
                }

            }
        
            void pop()
            {
                std::swap(_con[0],_con[_con.size()-1]);

                _con.pop_back();

                adjust_down(0);
            }


    };
};
